Skip to main content

Rotate Array

Problem Description​

Given an unsorted array arr[] of size n. Rotate the array to the left (counter-clockwise direction) by d steps, where d is a positive integer.

Examples​

Example 1:

Input:
n = 5, d = 2
arr = [1, 2, 3, 4, 5]
Output: [3, 4, 5, 1, 2]
Explanation: After rotating the array by 2 positions to the left, the array becomes [3, 4, 5, 1, 2].

Example 2:

Input:
n = 7, d = 3
arr = [2, 4, 6, 8, 10, 12, 14]
Output: [8, 10, 12, 14, 2, 4, 6]
Explanation: After rotating the array by 3 positions to the left, the array becomes [8, 10, 12, 14, 2, 4, 6].

Your Task​

You don't need to read input or print anything. Your task is to complete the function rotateArr() which takes the array arr, integer d and integer n, and rotates the array by d elements to the left.

Expected Time Complexity: O(n)O(n)

Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1 ≤ n ≤ 10^7
  • 1 ≤ d ≤ n
  • 0 ≤ arr[i] ≤ 10^5

Problem Explanation​

The task is to rotate an array to the left by d elements. Rotating an array means shifting all elements to the left by a given number of positions, and the elements that fall off the start of the array reappear at the end.

Code Implementation​

C++ Solution​

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{
public:
//Function to rotate an array by d elements in counter-clockwise direction.
void rotateArr(int arr[], int d, int n){
// Edge case: if d is 0 or d equals n, array remains unchanged
if(d == 0 || d == n)
return;

// Normalize d if it's greater than n
d = d % n;

// Reverse the first d elements
reverse(arr, arr + d);

// Reverse the remaining n-d elements
reverse(arr + d, arr + n);

// Reverse the entire array
reverse(arr, arr + n);
}
};

//{ Driver Code Starts.

int main() {
int t;
//taking testcases
cin >> t;

while(t--){
int n, d;

//input n and d
cin >> n >> d;

int arr[n];

//inserting elements in the array
for(int i = 0; i < n; i++){
cin >> arr[i];
}
Solution ob;
//calling rotateArr() function
ob.rotateArr(arr, d, n);

//printing the elements of the array
for(int i =0; i < n; i++){
cout << arr[i] << " ";
}
cout << endl;
}
return 0;
}
// } Driver Code Ends

Example Walkthrough​

Example 1:

For the input:

n = 5, d = 2
arr = [1, 2, 3, 4, 5]
  1. Rotate the first d elements: [2, 1, 3, 4, 5]
  2. Rotate the remaining n-d elements: [2, 1, 5, 4, 3]
  3. Rotate the entire array: [3, 4, 5, 1, 2]

Example 2:

For the input:

n = 7, d = 3
arr = [2, 4, 6, 8, 10, 12, 14]
  1. Rotate the first d elements: [6, 4, 2, 8, 10, 12, 14]
  2. Rotate the remaining n-d elements: [6, 4, 2, 14, 12, 10, 8]
  3. Rotate the entire array: [8, 10, 12, 14, 2, 4, 6]

Solution Logic:​

  1. Use three reverse operations:
    • Reverse the first d elements.
    • Reverse the remaining n-d elements.
    • Reverse the entire array.
  2. This approach ensures that the elements are shifted in place with an O(n)O(n) time complexity and O(1)O(1) auxiliary space.

Time Complexity​

  • The time complexity is O(n)O(n) as the array is processed three times.

Space Complexity​

  • The auxiliary space complexity is O(1)O(1) as no additional storage is used.

References​